/**
 * [15] 三数之和
 * 双指针算法思路：
 * # 先排序再用双指针
 * @format
 * @lc app=leetcode.cn id=15 lang=javascript
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */

// 双指针：我的
var threeSum = function (nums) {
    const triples = []
    if (nums == null || nums.length < 3) return triples // 优化
    nums.sort((a, b) => a - b)
    for (let i = 0; i < nums.length - 2; i++) {
        if (nums[i] > 0) break // 优化
        if (i > 0 && nums[i] == nums[i - 1]) continue // 去重
        let [left, right] = [i + 1, nums.length - 1]
        while (left < right) {
            const SUM = nums[left] + nums[i] + nums[right]
            if (SUM == 0) {
                // const id = [nums[left], nums[i], nums[right]].join("")
                // if (!flags[id]) {
                //     triples.push([nums[left], nums[i], nums[right]])
                //     flags[id] = true
                // }
                triples.push([nums[left], nums[i], nums[right]])
                while (left < right && nums[left] == nums[left + 1]) left++ // 去重
                while (left < right && nums[right] == nums[right - 1]) right-- // 去重
                left++
                right--
            } else if (SUM < 0) left++
            else right--
        }
    }
    return triples
}
debugger
console.log(threeSum([3, 0, -2, -1, 1, 2]))

// 双指针：大佬的
var threeSum = function (nums) {
    let ans = []
    const len = nums.length
    if (nums == null || len < 3) return ans
    nums.sort((a, b) => a - b) // 排序
    for (let i = 0; i < len; i++) {
        if (nums[i] > 0) break // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
        if (i > 0 && nums[i] == nums[i - 1]) continue // 去重
        let L = i + 1
        let R = len - 1
        while (L < R) {
            const sum = nums[i] + nums[L] + nums[R]
            if (sum == 0) {
                ans.push([nums[i], nums[L], nums[R]])
                while (L < R && nums[L] == nums[L + 1]) L++ // 去重
                while (L < R && nums[R] == nums[R - 1]) R-- // 去重
                L++
                R--
            } else if (sum < 0) L++
            else if (sum > 0) R--
        }
    }
    return ans
}

// 作者：画手大鹏
// 链接：https://leetcode.cn/problems/3sum/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

// 暴力算法
// var threeSum = function (nums) {
//     const [triples, flags] = [[], {}]
//     let id = ""
//     for (let i = 0; i < nums.length - 2; i++) {
//         for (let j = i + 1; j < nums.length - 1; j++) {
//             for (let k = j + 1; k < nums.length; k++) {
//                 id = [nums[i], nums[j], nums[k]].sort().join("")
//                 if (nums[i] + nums[j] + nums[k] == 0 && !flags[id]) {
//                     flags[id] = true
//                     triples.push([nums[i], nums[j], nums[k]])
//                 }
//             }
//         }
//     }
//     return triples
// }
// @lc code=end
